The present invention relates to the field of circuits for shifting data, and more particularly, the present invention relates to barrel rotators.
A barrel shifter is a digital circuit that can shift a data word or an ordered list of elements by a specified number of bits or positions in a single clock cycle. A sub-category of barrel shifters is the barrel rotators, which are circuits that perform circular-shift operations. A circular, or cyclic, shift is the operation of rearranging the entries in an ordered list of elements, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. The result of repeatedly applying s circular shifts to a given set of entries is called a circular shift by s positions. Shifting and rotating data is required in several applications including arithmetic operations, variable-length coding, and bit-indexing. Barrel rotators are often utilized by embedded digital signal processors and general-purpose processors to manipulate data.
Barrel rotators are widely used in Low Density Parity Check (LDPC) decoders. LDPC codes are a subcategory of linear block error correction codes characterized by a sparse parity check matrix. This means that the parity check matrix consists mainly of 0's and a relatively small number of 1's. LDPC codes were first introduced in the 1960's but have more recently received increased attention. This is due at least in part to inherent parallelism in decoding which makes LDPC codes suitable for hardware implementation and due to flexibility in designing LDPC codes, which allows LDPC codes to be used in a variety of applications.
A bipartite Tanner graph is a widely used way to represent a parity check matrix H. This graph consists of two sets of nodes, namely the check nodes and the variable nodes. Each row of H corresponds to a parity check equation, graphically represented as a check node of the Tanner graph, while columns correspond to the codeword bits, graphically represented as variable nodes. An ace in the H matrix indicates a connection between the corresponding variable and check nodes. Message passing algorithms for decoding LDPC codes operate by iteratively passing information along the edges of the Tanner graph. In a sense, the variable nodes correspond to bits of a received word—both message and parity—while check nodes correspond to parity check equations.
Decoding of LDPC codes often requires shift or shuffle operations to route information between processing elements or to/from memories. This is particularly true for some kinds of LDPC codes, including Quasi-Cyclic LDPC (QC-LDPC) codes. QC-LDPC codes are a subcategory of LDPC codes characterized by parity check matrices comprised of square sub-matrices. Each of these sub-matrices is either a z×z zero sub-matrix or a z×z right circularly shifted identity sub-matrix. FIG. 7 represents a 6×6 identity sub-matrix right circularly shifted by 2 columns. FIG. 8 illustrates the code-rate-1/2, 648-bit code defined in the IEEE 802.11n and the IEEE 802.11ac standards, in a compact form. The actual parity check matrix of this code-rate-1/2, 648-bit LDPC code, is derived from this compact representation by replacing each −1 value by the z×z zero sub-matrix, where z=27, and each s value equal or greater than 0, by a z×z identity sub-matrix right circularly shifted by s columns. We call value s rotate factor of the corresponding square sub-matrix, and sε{0, 1, . . . , z−1}. FIG. 9 represents the code-rate-1/2, 1296-bit code and FIG. 10 represents the code-rate-1/2, 1944-bit code of the IEEE 802.11n/ac standards. The standards support twelve different LDPC codes. More specifically, three codeword lengths (648, 1296, 1944) and four coding rates (1/2, 2/3, 3/4, 5/6) are supported. Generally, the dimensions of a code-rate-r, nc-bit code of the IEEE 802.11n/ac standards is given by (24·(1−r)·z)×nc, where nc=24·z. The value z is equal to 27 in case nc is equal to 648, z=54 in case nc=1296 and z=81 in case nc=1944. The barrel rotator is a well-known circuit designed to perform all the permutations of its inputs obtainable with a circular shift operation (rotations), thus being well suited for the circularly shifted structure of the QC-LDPC H matrix.
QC-LDPC codes are widely used in error correction systems due to resulting lower hardware complexity and comparable performance to randomly constructed codes. The particular structure of the QC-LDPC codes ensures that there is at most one unique ace in every column of the z×z square sub-matrices which compose these codes. This allows the parallel processing of up to z lines of the parity check matrix without data conflicts. As mentioned before and depicted in FIG. 8, in an implementation of an LDPC decoder circuit each row of H corresponds to a check node processing element, while columns correspond to variable node processing elements. A barrel rotator is a suitable circuit to realize the rotations of the QC-LDPC sub-matrices. These rotations define the interconnection between the basic processing elements of a QC-LDPC decoder which are the variable node processing elements and the check node processing elements. There is a variety of partially-parallel QC-LDPC decoder implementations, where there is a necessity of an efficient permutation network, able to interconnect a number of n variable node processing elements with n check node processing elements.
Telecommunication standards, such as WiMAX and WiFi, support a variety of codes. An LDPC decoder architecture suitable for the 802.11n/ac IEEE standards would ideally support three codeword lengths (648, 1296, 1944) and four coding rates (1/2, 2/3, 3/4, 5/6) in order to implement the twelve LDPC parity check matrices defined by the standard. To accommodate multiple codes of different characteristics, such as length, rate, and check degrees of each parity check matrix, there is a need for a reconfigurable interconnection network that efficiently realizes connectivity between variable and check node processors of a decoder.